class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None


# 前序 根左右
def preorder_dg(root):
    if not root:
        return 
    print(root.val)
    preorder_dg(root.left)
    preorder_dg(root.right)

def preorder_dd(root):
    stack = [root]
    while stack:
        s = stack.pop()
        if s:
            print(s.val)
            stack.append(s.right)
            stack.append(s.left)


# 中序 左根右
def midorder_dg(root):
    if not root:
        return 
    midorder_dg(root.left)
    print(root.val)
    midorder_dg(root.right)

def midorder_dd(root):
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        print(root.val)
        root = root.right


# 后序 左右根
def posorder_dg(root):
    if not root:
        return 
    posorder_dg(root.left)
    posorder_dg(root.right)
    print(root.val)


# 层次遍历
def BFS(root):
    queue = [root]
    while queue:
        n = len(queue)
        for i in range(n):
            q = queue.pop(0)
            if q:
                print(q.val)
                queue.append(q.left if q.left else None)
                queue.append(q.right if q.right else None)


# 二叉树的最大深度
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
 

if __name__ == "__main__":
    root = TreeNode("A")
    root.left = TreeNode("B")
    root.right = TreeNode("C")
    root.left.left = TreeNode("D")
    root.left.right = TreeNode("E")
    root.right.right = TreeNode("F")

    print("前序")
    preorder_dg(root)
    print()
    preorder_dd(root)
    print("中序")
    midorder_dg(root)
    print()
    midorder_dd(root)
    print("后序")
    posorder_dg(root)

    # a = [1, 2, 3]
    # while a:
    #     b = a.pop()
    #     print(b)


